﻿namespace Leetcode.N0131;

public class Solution
{
    public IList<IList<string>> Partition(string s)
    {
        var partitions = new IList<IList<string>>[s.Length];
        var flgs = new bool[s.Length][];

        for (int i = s.Length - 1; i >= 0; i--)
        {
            var partitionsItem = new List<IList<string>>();
            flgs[i] = new bool[s.Length];
            partitions[i] = partitionsItem;

            for (int j = i; j < s.Length; j++)
            {
                var r = this.Partition(s, i, j, partitions, flgs);
                flgs[i][j] = r.flg;
                partitionsItem.AddRange(r.partitions);
            }
        }

        return partitions[0];
    }

    private (bool flg, IList<IList<string>> partitions) Partition(string s, int from, int to, IList<IList<string>>[] partitions, bool[][] flgs)
    {
        List<IList<string>> curPartions = new List<IList<string>>();
        var flg = false;
        if (s[from] == s[to])
        {
            var sFromTo = s.Substring(from, to - from + 1);

            var subFrom = from + 1;
            var subTo = to - 1;
            flg = (subFrom > subTo || subFrom >= s.Length || subTo < 0) ? true : flgs[subFrom][subTo];

            if (flg)
            {
                curPartions = new List<IList<string>>();
                if (to < s.Length - 1)
                {
                    var subPartitions = partitions[to + 1];
                    curPartions.AddRange(subPartitions.Select(i =>
                                       {
                                           var l = new List<string>() { sFromTo };
                                           l.AddRange(i.ToArray());
                                           return l;
                                       }));
                }
                else
                {
                    curPartions.Add(new List<string>() { sFromTo });
                }
            }
        }

        return (flg, curPartions);
    }
}